\documentclass[compress,mathserif,table]{beamer}

\usetheme{Peking} %% Madrid, Malmoe, Warsaw, Marburg

\usepackage{amsmath,amsfonts,amssymb,hyperref,pict2e}
\usepackage{subfigure,graphicx}
\usepackage{color}
\usepackage{tikz}

\setbeamercovered{transparent}
\setbeamertemplate{navigation symbols}{}   
\begin{document}

\title{Parallel GEMM on FPGA}
\author{WANG, Pei\\LU, Xiaobo\\LI, Chen}
\institute{School of Electronics Enginerring and Computer Science\\Peking University}
\date{\today}

\begin{frame}
  \titlepage
\end{frame}

\begin{frame}
  \frametitle{Outline}
  \tableofcontents
  % You might wish to add the option [pausesections]
\end{frame}

\AtBeginSection[] {
  \begin{frame}<beamer>
    \frametitle{Outline}
    \tableofcontents[currentsection]
  \end{frame}
}

\AtBeginSubsection[] {
  \begin{frame}<beamer>
    \frametitle{Outline}
    \tableofcontents[currentsection,currentsubsection]
  \end{frame}
}


\section{Background}

\begin{frame}
\frametitle{What Is GEMM}
\begin{itemize}
\item The General Matrix Multiply (GEMM) is a subroutine in the \textit{Basic Linear Algebra Subprograms (BLAS)} which performs matrix multiplication, that is the multiplication of two matrices.
\item GEMM is often tuned by High Performance Computing vendors to run as fast as possible, because it is the building block for so many other routines. It is also the most important routine in the LINPACK benchmark. For this reason, implementations of fast BLAS library typically focus first on GEMM performance.
\end{itemize}
\begin{flushright}
  \tiny\textit{from WikiPedia}
\end{flushright}
\end{frame}

\begin{frame}
\frametitle{Who Cares For GEMM}
\begin{figure}
  \centering
  \includegraphics[width=1.0\textwidth]{figures/top500.png}
  \caption{Super computer performance}
\end{figure}
\begin{flushright}
  \tiny\textit{from top500.org}
\end{flushright}
\end{frame}

\begin{frame}
\frametitle{Who Cares For GEMM}
\begin{figure}
  \centering
  \begin{tabular}{cc}
    \includegraphics[width=.3\textwidth]{figures/mathsworks-logo.jpg} &
    \includegraphics[width=.22\textwidth]{figures/ps-logo.png}\\
    \includegraphics[width=.35\textwidth]{figures/scilab-logo.png} &
    \includegraphics[width=.3\textwidth]{figures/sas-logo.jpg}\\
  \end{tabular}
  \caption{Software applying GEMM}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{GEMM on FPGA}
\begin{itemize}
\item Not a new topic
\item FPGA usually as acceleration unit
\item Parallelism is important
\end{itemize}
\end{frame}

\section{Design}
\subsection{Methodology}
\begin{frame}
\frametitle{Acceraltion Methodologies}
\begin{figure}
  \centering
  \begin{tabular}{cc}
    \includegraphics[width=.45\textwidth]{figures/theory.jpg} &
    \includegraphics[width=.4\textwidth]{figures/practice.jpg}\\
  \end{tabular}
  \caption{Two different methodologies}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{Theoretical Approach}
\begin{itemize}
\item For decreasing computational complexity of matrix multiplication.
\item Examples
\end{itemize}
\vspace{0in}
\begin{figure}
  \centering
  \begin{tabular}{cc}
  Algorithm & Complexity \\
  \hline
  Trivial   & $O(n^3)$   \\
  Strassen  & $O(n^{log_27})$ \\
  Coppersmith-Winograd & $O(n^{2.376})$ \\
  \end{tabular}
  \caption{Different algorithms for matrix muliplication}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{Theoretical Approach}
\begin{exampleblock}{Pros}
  \begin{itemize}
  \item Sounds COOL! (significant if you want to sell something)
  \item Always more efficient when data amount grows large enough
  \end{itemize}
\end{exampleblock}
\begin{alertblock}{Cons}
  \begin{itemize}
  \item Data amount is usually not that large
  \item Hard to implement (especially for hardware)
  \item Many complex alogorithms lack numerical stability
  \end{itemize}
\end{alertblock}
\end{frame}

\begin{frame}
\frametitle{Practical Approach}

\begin{center}
  \Huge \textbf{Let Real Time Speak!}
\end{center}

\begin{itemize}
\item Focus on runtime performance
\item Complexity is not a issue
\item Architecture of computing platform is IMPORTANT
\item Our way to go
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Practical Approach}
\begin{center}
  A practical case of parallel GEMM on GPGPU
\end{center}
\begin{figure}
  \centering
  \begin{tabular}{cc}
    \includegraphics[width=.4\textwidth]{figures/cuda-model.png} &
    \includegraphics[width=.4\textwidth]{figures/cuda-memory.jpg} \\
  \end{tabular}
  \caption{Nvidia CUDA architecture}
\end{figure}
\begin{flushright}
  \tiny \textit{from Nvidia}
\end{flushright}
\end{frame}

\begin{frame}
\frametitle{Practical Approach}
\begin{center}
  Improve throughput by coalescing memory access
\end{center}

\begin{figure}
  \centering
  \includegraphics[width=1.0\textwidth]{figures/mem-access-gpu-co.png}
  \caption{Example of coalesced memory access}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{Practical Approach}
\begin{figure}
  \centering
  \includegraphics[width=.4\textwidth]{figures/cuda-matrix.png}
  \caption{Use sub-block routines to accelerate matrix multiplication}
\begin{flushright}
  \tiny \textit{from Nvidia}
\end{flushright}
For detailed algorithm and evaluation, go for \\{\tiny Vasily Volkov, James W. Demmel: \textbf{Benchmarking GPUs to Tune Dense Linear Algebra}, \textit{SC'08}}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{What Do We Do}
\begin{itemize}
\item Improve performance by parallelism
  \begin{itemize}
  \item Very suitable task for FPGA
  \item Low data dependecy of GEMM
  \item Colok-level computing makes sychronization problem easy to address
  \end{itemize}
\item Improve throughput by carefully managed mem-access
  \begin{itemize}
  \item Memory design is somewhat more flexible on FPGA
  \item Reading and writing patterns for different granularities
  \end{itemize}
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Design Overview}
\usetikzlibrary{arrows,shapes}

\tikzstyle{transfer} = [draw,thin,fill=blue!20]
\tikzstyle{main} = [rectangle,draw,thin,fill=green!20]
\tikzstyle{sub} = [ellipse,draw,thin,fill=red!20]

\begin{figure}
  \begin{tikzpicture}[node distance=2cm, auto, thick]
    \path[->] node[transfer] (recv) {receiver};
    \path[->] node[main, right of=recv] (cal) {calculator}
                  (recv) edge (cal);
    \path[->] node[transfer, right of=cal] (send) {sender}
                  (cal)  edge (send);
    \path node[sub, below of=cal] (subunit) {64 cal-units}
                  (subunit) edge (cal);
  \end{tikzpicture}
  \caption{64-64 matrix multiplier on FPGA}
\end{figure}
\end{frame}

\subsection{Algorithm}

\begin{frame}
\frametitle{Key Component}
\begin{itemize}
\item 64 calculating units
\item A buffer for intermediate results
\item Memory blocks with high bus width
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Work Flow}
\begin{figure}
  \begin{tikzpicture}[node distance=0cm, auto, thick]
    \renewcommand{\u}{0.8}
    \tikzstyle{grid}=[rectangle,draw,minimum width=.8cm, minimum height=.8cm, text centered]
    \tikzstyle{blank}=[rectangle,minimum width=.8cm, minimum height=.8cm, text centered, fill=black!0]
    \tikzstyle{normal}=[grid, fill=black!10]
    \tikzstyle{focus}=[grid, fill=yellow!60]
    \tikzstyle{read}=[grid, fill=blue!60]
    \tikzstyle{cal}=[grid, fill=red!60]
    \tikzstyle{write}=[grid, fill=green!60]
    % prepare
    \path <1-1> node[normal] (c11) at (4*\u,7*\u) {c11};
    \path <1-1> node[normal] (c12) at (5*\u,7*\u) {c12};
    \path <1-1> node[normal] (c21) at (4*\u,6*\u) {c21};
    \path <1-1> node[normal] (c22) at (5*\u,6*\u) {c22};

    \path <1-1> node[normal] (a11) at (1*\u,4*\u) {a11};
    \path <1-1> node[normal] (a12) at (1*\u,3*\u) {a12};
    \path <1-1> node[normal] (a21) at (0,4*\u) {a21};
    \path <1-1> node[normal] (a22) at (0,3*\u) {a22};

    \path <1-1> node[normal] (b11) at (4*\u,1*\u) {b11};
    \path <1-1> node[normal] (b12) at (5*\u,1*\u) {b12};
    \path <1-1> node[normal] (b21) at (4*\u,0) {b21};
    \path <1-1> node[normal] (b22) at (5*\u,0) {b22};

    % begin
    \path <2-3> node[write]  (c11) at (4*\u,7*\u) {c11};
    \path <2-3> node[write]  (c12) at (5*\u,7*\u) {c12};
    \path <2-3> node[normal] (c21) at (4*\u,6*\u) {c21};
    \path <2-3> node[normal] (c22) at (5*\u,6*\u) {c22};

    \path <4-5> node[normal] (c11) at (4*\u,7*\u) {c11};
    \path <4-5> node[normal] (c12) at (5*\u,7*\u) {c12};
    \path <4-5> node[write]  (c21) at (4*\u,6*\u) {c21};
    \path <4-5> node[write]  (c22) at (5*\u,6*\u) {c22};


    \path <2-2> node[read]   (a11) at (1*\u,4*\u) {a11};
    \path <2-3> node[normal] (a21) at (0,4*\u) {a21};
    \path <3-3> node[focus]  (a11) at (1*\u,4*\u) {a11};
    \path <2-3> node[normal] (a22) at (0,3*\u) {a22};
    \path <2-2> node[focus]  (a12) at (1*\u,3*\u) {a12};
    \path <3-3> node[read]   (a12) at (1*\u,3*\u) {a12};

    \path <4-5> node[normal] (a11) at (1*\u,4*\u) {a11};
    \path <4-5> node[normal] (a12) at (1*\u,3*\u) {a12};
    \path <4-4> node[read]   (a21) at (0,4*\u) {a21};
    \path <5-5> node[focus]  (a21) at (0,4*\u) {a21};
    \path <4-4> node[focus]  (a22) at (0,3*\u) {a22};
    \path <5-5> node[read]   (a22) at (0,3*\u) {a22};

    \path <2,4> node[focus]  (b11) at (4*\u,1*\u) {b11};
    \path <2,4> node[focus]  (b12) at (5*\u,1*\u) {b12};
    \path <2,4> node[normal] (b21) at (4*\u,0) {b21};
    \path <2,4> node[normal] (b22) at (5*\u,0) {b22};

    \path <3,5> node[normal] (b11) at (4*\u,1*\u) {b11};
    \path <3,5> node[normal] (b12) at (5*\u,1*\u) {b12};
    \path <3,5> node[focus]  (b21) at (4*\u,0) {b21};
    \path <3,5> node[focus]  (b22) at (5*\u,0) {b22};

    \path <2-5> node[cal] (u1) at (4*\u, 3.5*\u) {$\times$};
    \path <2-5> node[cal] (u2) at (5*\u, 3.5*\u) {$\times$};

    \path[->] <2-2> (a11) edge[bend right] (u1);  
    \path[->] <2-2> (a11) edge[bend left] (u2);
    \path[->] <3-3> (a12) edge[bend left] (u1);   
    \path[->] <3-3> (a12) edge[bend right] (u2);

    \path[->] <4-4> (a21) edge[bend right] (u1);   
    \path[->] <4-4> (a21) edge[bend left] (u2);
    \path[->] <5-5> (a22) edge[bend left] (u1);    
    \path[->] <5-5> (a22) edge[bend right] (u2);

    \path[->] <2,4> (b11) edge (u1);
    \path[->] <2,4> (b12) edge (u2);
    \path[->] <3,5> (b21) edge[bend left] (u1);
    \path[->] <3,5> (b22) edge[bend right] (u2);
    
    \path[->] <2-3> (u1) edge[bend left] node{+} (c11);
    \path[->] <2-3> (u2) edge[bend right] node{+} (c12);
    \path[->] <4-5> (u1) edge node{+} (c21);
    \path[->] <4-5> (u2) edge node{+} (c22);
  \end{tikzpicture}
\end{figure}
\end{frame}


\begin{frame}
\frametitle{Algorithm Summary}
\begin{itemize}
\item True parrallel
\item No explicit synchronization
\item Complexity of $O(n^2)$
\item Improve performance with limited memory access
\end{itemize}
\end{frame}

\subsection{Implementation}
\begin{frame}
\frametitle{Memory}
\begin{itemize}
\item Data amount: $64 \times 64 \times 32 \times 3 = 384$(Kbit)
\item Use block memory
\item Combine two $1024\times 64$ memories to store a matrix
\item Module from IP Core Generator
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Buffer}
\begin{itemize}
\item 2048 bits
\item Make asymmetric reading and writing possible
\item Mapped to LUT
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{I/O}
\begin{itemize}
\item Device has only 640 pins
\item Use serial I/O
\item Another 2048-bit buffer is needed
\end{itemize}
\end{frame}

\subsection{Verification}
\begin{frame}
\frametitle{Simulation}
\begin{itemize}
\item Test passed in simulation
\item Post-layout simulation pending
\item Design not implemented on physical device yet
\end{itemize}
\end{frame}


\section{Evaluation}

\begin{frame}
\frametitle{Device Utilization}
\begin{figure}
  \centering
  \includegraphics[width=.6\textwidth]{figures/utilization.png}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{Bottleneck}
\begin{alertblock}{What Consumes Resources}
  2048-bit buffers use too many LUTs
\end{alertblock}
\begin{itemize}
\item Make maping and routing difficult: more than 7 hours
\item Undoubtedly affect the performance
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Performance}
\begin{center}
  \Huge TBD
\end{center}
\end{frame}

\begin{frame}
\frametitle{Last Slide}
\begin{center}
  \Huge Q\&A
\end{center}
\end{frame}

\end{document}
